package org.usmile.algorithms.leetcode.hard;

/**
 * 493. 翻转对
 *
 * 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
 * 你需要返回给定数组中的重要翻转对的数量。
 *
 * 示例 1:
 * 输入: [1,3,2,3,1]
 * 输出: 2
 *
 * 示例 2:
 * 输入: [2,4,3,5,1]
 * 输出: 3
 *
 * 注意:
 * 给定数组的长度不会超过50000。
 * 输入数组中的所有数字都在32位整数的表示范围内。
 */
public class _0493 {
}

class _0493_Solution {
    int[] nums;
    int count;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        this.count = 0;

        mergeSort(0, nums.length - 1);

        return count;
    }

    private void mergeSort(int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        int i = left;
        int j = mid + 1;
        while (i <= mid) {
            while (j <= right && (long)nums[i] > (long)nums[j] * 2) {
                j++;
            }
            count += (j - mid - 1);
            i++;
        }

        merge(left, mid, right);
    }

    private void merge(int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (k < temp.length) {
            if (i == mid + 1) {
                temp[k++] = nums[j++];
            } else if (j == right + 1) {
                temp[k++] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        for (k = 0; k < temp.length; k++) {
            nums[left++] = temp[k];
        }
    }
}
